package main

func leastBricks(wall [][]int) int {
	result := 1 << 32
	//一个二维数组记录哪里不需要穿墙
	//dp:=make([][]bool,len(wall))
	tempMap := make(map[int]map[int]bool)
	totalLen := 0
	for _, value := range wall[0] {
		totalLen += value
	}
	minLen := 1 << 32
	for index, column := range wall {
		tempLen := 0
		//dp[index]=make([]bool,totalLen+1)
		tempMap[index] = make(map[int]bool)
		for _, row := range column {
			tempLen += row
			//dp[index][tempLen]=true
			tempMap[index][tempLen] = true
			minLen = min(minLen, row)
		}
	}

	for i := 0; i < totalLen; i = i + minLen {
		needWall := 0
		for j := 0; j < len(wall); j++ {
			if _, ok := tempMap[j][i]; !ok {
				needWall++
			}
		}
		result = min(result, needWall)
	}
	return result
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
